package org.liaohailong.helloworld.array;

import java.util.LinkedList;

/**
 * Author: liaohailong
 * Date: 2021/5/29
 * Time: 10:57
 * Description:
 **/
public class ArraySolution {

    // LC 寻找数组的中心索引
    public int pivotIndex(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;

        int left = 0;


        int pi = -1;
        int pos = -1;
        while (true) {
            pos++;
            if (pos >= nums.length) break;
            if (pos >= 1) left += nums[pos - 1];
            int rightMid = total - left;
            int right = rightMid - nums[pos];
            if (left == right) {
                pi = pos;
                break;
            }
        }
        return pi;
    }

    // LC 搜索插入位置
    public int searchInsert(int[] nums, int target) {
        // 二分法查找
        int start = 0;
        int end = nums.length - 1;
        while (true) {
            int span = end - start;
            int mid = start + (span) / 2;
            int midVal = nums[mid];
            if (midVal == target) {
                // 找到
                return mid;
            } else if (midVal < target) {
                // 右边
                start = mid;
            } else if (midVal > target) {
                // 左边
                end = mid;
            }

            // 不存在数组中，插入排序
            // 1，end就是target的位置
            // 2，target小于start，在左边
            // 3，target大于end，在右边
            if (end - start <= 1) {
                if (target <= nums[start]) {
                    return start;
                } else if (target > nums[end]) {
                    return end + 1;
                } else if (target == nums[end])
                    return end;
                else return end;
            }
        }
    }

    // LC 合并区间
    public int[][] merge(int[][] intervals) {
        if (intervals.length < 2) return intervals;
        quickSort(intervals, 0, intervals.length - 1);

        LinkedList<int[]> list = new LinkedList<>();
        int min = intervals[0][0];
        int max = intervals[0][1];
        int pos = 0;
        do {
            pos++;
            if (intervals[pos][0] <= max) {
                // 有交集，要融入
                max = Math.max(intervals[pos][1], max);
            } else {
                // 无交集，上一段独立，这一块做比较
                list.add(new int[]{min, max});
                min = intervals[pos][0];
                max = intervals[pos][1];
            }
        } while (pos < intervals.length - 1);
        // don't forget last pair
        list.add(new int[]{min, max});

        int[][] result = new int[list.size()][2];
        pos = -1;
        for (int[] ints : list) {
            pos++;
            result[pos][0] = ints[0];
            result[pos][1] = ints[1];
        }
        return result;
    }

    private void quickSort(int[][] arr, int start, int end) {
        if (start < end) {
            int mid = partition(arr, start, end);
            quickSort(arr, start, mid);
            quickSort(arr, mid + 1, end);
        }
    }

    private int partition(int[][] arr, int start, int end) {
        int[] temp = arr[start];
        int left = start;
        int right = end;

        while (left < right) {
            while (arr[right][0] >= temp[0] && left < right) right--;
            if (left < right) {
                arr[left] = arr[right];
                left++;
            }
            while (arr[left][0] <= temp[0] && left < right) left++;
            if (left < right) {
                arr[right] = arr[left];
                right--;
            }
        }
        arr[left] = temp;
        return left;
    }

    // LC 旋转矩阵 NxN矩阵
//    public void rotate(int[][] matrix) {
//        if (matrix.length < 2) return; // 无需移动
//        int N = matrix.length;
//        int[][] result = new int[N][N];
//        int count = matrix.length / 2; // 维度
//        // 尺寸是奇数，补充中间
//        if (matrix.length % 2 == 1) {
//            int mid = matrix.length / 2;
//            result[mid][mid] = matrix[mid][mid];
//        }
//
//        for (int i = 0; i < count; i++) {
//            // 范围缩小
//            int len = N - i;
//            int last = len - 1;
//            int start = i;
//            for (int j = i; j < len; j++) {
//                int r = last;// 右
//                int b = last;// 下
//                int l = start;// 左
//                int t = start;// 上
//
//                result[j][r] = matrix[t][j];// 上转右
//                result[b][l + last - j] = matrix[j][r];// 右转下
//                result[j][l] = matrix[b][j];// 下转左
//                result[t][l + last - j] = matrix[j][l]; // 左转上
//            }
//        }
//
//        for (int i = 0; i < N; i++) {
//            System.arraycopy(result[i], 0, matrix[i], 0, N);
//        }
//    }


    // LC 旋转矩阵 NxN矩阵
    public void rotate(int[][] matrix) {
        // 沿对角线 leftTop rightBottom
        int N = matrix.length;

        //1. 对角翻转
        for (int row = 0; row < N; row++) {
            for (int column = 0; column <= row; column++) {
                swap(matrix, row, column, column, row);
            }
        }
        // 2. 镜像翻转
        for (int row = 0; row < N; row++) {
            for (int column = 0; column < N / 2; column++) {
                swap(matrix, row, column, row, N - column - 1);
            }
        }
    }

    private void swap(int[][] matrix, int x0, int y0, int x1, int y1) {
        int temp = matrix[x0][y0];
        matrix[x0][y0] = matrix[x1][y1];
        matrix[x1][y1] = temp;
    }

    // LC 零矩阵
    public void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length];
        boolean[] column = new boolean[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    column[j] = true;
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (row[i] || column[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    // LC 对角线遍历
    public int[] findDiagonalOrder(int[][] mat) {
        int row = mat.length;
        int column = mat[0].length;
        int count = row * column;
        int[] result = new int[row * column];
        int x = 0;
        int y = 0;
        boolean up = true;
        int[] point = new int[2];

        int pos = -1;
        while (true) {
            pos++;
            result[pos] = mat[y][x];
            if (pos >= count - 1) break; // add last one
            nextPoint(up, x, y, point);
            if (inBounds(mat, point[0], point[1])) {
                x = point[0];
                y = point[1];
            } else {
                // adjust point
                if (up) {
                    // y超出，判断x
                    if (point[1] < 0) {
                        if (point[0] < column) {
                            // x不变
                            y = 0;
                            x = point[0];
                        } else {
                            x = column - 1;
                            y = point[1] + 2;
                        }
                    }
                    // x超出
                    else if (point[0] > column - 1) {
                        x = column - 1;
                        y = point[1] + 2;
                    }
                } else {
                    // x超出
                    if (point[0] < 0) {
                        if (point[1] < row) {
                            // y不变
                            x = 0;
                            y = point[1];
                        } else {
                            y = row - 1;
                            x = point[0] + 2;
                        }
                    }
                    // y超出，判断x
                    else if (point[1] > row - 1) {
                        y = row - 1;
                        x = point[0] + 2;
                    }
                }
                up = !up;
            }
        }

        return result;
    }

    private void nextPoint(boolean up, int x, int y, int[] p) {
        if (up) {
            x = x + 1;
            y = y - 1;
        } else {
            x = x - 1;
            y = y + 1;
        }
        p[0] = x;
        p[1] = y;
    }

    private boolean inBounds(int[][] mat, int x, int y) {
        if (x < 0 || y < 0) return false;
        return y < mat.length && x < mat[y].length;
    }
}
